0x02 COCI 2016-2017

T1

将每一位 $#$ 按顺序拼在一起，可知这个子串决定了字符串的字典序
相当于一个每一位都是不同进制的数字，按照每个 $#$ 对应的长度分解得到答案

已知要组成回文数组，可以发现：从左数 $i$ 个数的和与从右数 $i$ 个数的和一定相等

于是可以双指针找前缀与后缀和，
左右不相等时，扩充和更小那一边的范围，并且操作次数加一
否则同时扩充两边范围，相遇（相等）时停止

可以证明不存在其它能够构造出更长数组的方案

注意到范围只有 $20$ ，考虑状压

记录 $f_i$ 为状态 $i$ 下的最小代价
定义状态 $i$ 为：若 (i>>j)&1 为 $1$ ，则第 $j$ 个杯子里没有水

注意到可以每次一定可以进行一次操作，使一个非空杯子变空
这个操作的代价只与初状态和改变的位数有关，也可以说只与初状态和末状态有关，而与之前的操作方法无关
因此每次可以将状态 $i$ 的一个 $0$ 变为 $1$ ，来转移答案

将字符串反转，那么后缀就变成了前缀

所谓『押韵』，就是相邻字符串前缀相同，长度差不超过 $1$ ，并且： 1.在长度相同的情况下，最多有最后一位不同
2.在长度不同，即长度差为 $1$ 的情况下，短的字符串为长者的前缀

容易想到构建 $trie$ ，那么能够相邻的字符串： 1.在长度相同的情况下， $trie$ 上对应的节点为兄弟或相同节点
2.在长度不同情况下，短字符串对应节点是长字符串对应节点的父亲

也就是：相邻字符串对应一定为兄弟或父亲

注意到题干内容：保证字符串不同

因为相邻字符串长度变化量最多为 $1$ ，且互为父子
那么可以得到，当一个字符串的一个相邻字符串是它的父亲，那么这个字符串的另一个相邻节点一定是它的兄弟或它的儿子
即：这个字符串之后相邻的字符串长度只增不减
进一步得到，最长序列中的最短的字符串，向左与向右，字符串长度都一定单增

映射到 $trie$ 上，表现为字符串序列近似一条路径，从最低点分开，左右两个子序列（？，近似为一条树上的链
这条“链”上，每个深度的节点都是兄弟节点，且其中只有一个向更深的节点连边

考虑 $dfs$
我们将有对应字符串的节点称为有效节点，则：对于每个节点，我们假设当前节点为最低点
那么答案为子结点中能够向上延伸的极长链（不含子结点）的最大值，非严格次大值与有效子结点数量（兄弟节点之间一定可以相连）之和再加上自己
如果当前节点不有效，答案就不加上自己，而字符串序列仍然能够连续

而每个节点的极长链是容易维护的
注意非有效节点的极长链长度为 $0$

时间复杂度为 O(n) ，本地跑会爆栈空间，最高有 $3e6$ 层

linux/mac 环境需要在终端运行

ulimit -s unlimited

windows 环境编译时需要加上

g++ -std=c++14 -O2 -Wl,stack=998244353 test.cpp -o test.exe